package br.unicamp.integralization.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

import br.unicamp.integralization.dto.Allocation;
import br.unicamp.integralization.dto.History;
import br.unicamp.integralization.dto.Subject;
import br.unicamp.integralization.dto.SubjectGroup;

public class BestAllocator {
	
	//allocatedSubjects[i] indica qual o grupo em que a matéria i se encaixou
	//se ela for classificada como eletiva, será marcada com -1
	private static int[] allocatedSubjects;
	
	//Guarda todos os estados sem sucesso já pesquisados
	private static HashSet<String> evaluatedStates;
	
	//history do aluno
	private static History history;
	
	//subjectMatches[i][j] diz se a matéria j se encaixa no grupo i
	private static boolean[][] subjectMatches;
	
	//remainingGroupCredits[i][j] indica quantos créditos resta no grupo i
	//usando-se até a matéria j. (0,1,2...j)
	private static int[][] remainingGroupCredits;

	public static Allocation execute(History history) {
		evaluatedStates = new HashSet<String>();
		BestAllocator.history = history;


		// Removeremos as matérias obrigatorias
		// Elas serão obrigatoriamente colocadas no grupo das obrigatorias
		List<Subject> mandatoryDone = new ArrayList<Subject>();
		SubjectGroup mandatorySubjects = history.getAllocation()
				.getMandatorySubjects();
		for (Iterator<Subject> it = mandatorySubjects.getSubjects().iterator(); it
				.hasNext();) {
			Subject mandatorySubject = it.next();
			for (Iterator<Subject> jt = history.getSubjects().iterator(); jt
					.hasNext();) {
				Subject subject = jt.next();
				if (mandatorySubject.matches(subject)) {
					mandatoryDone.add(subject);
					jt.remove();
				}
			}

		}
		for (Subject subject : mandatoryDone) {
			System.out.print(subject+ " ");
		}

		List<SubjectGroup> electiveGroups = history.getAllocation()
				.getElectiveGroups();

		allocatedSubjects = new int[history.getSubjects().size()];
		Arrays.fill(allocatedSubjects, -1);

		
		subjectMatches = new boolean[electiveGroups.size()][];
		remainingGroupCredits = new int[electiveGroups.size()][history.getSubjects().size()];

		int sumOfCredits = 0;

		// Monta a matriz de matches dizendo se a matéria j encaixa no grupo i
		for (int i = 0; i < electiveGroups.size(); i++) {
			SubjectGroup group = electiveGroups.get(i);
			subjectMatches[i] = new boolean[history.getSubjects().size()];
			
			for (int j = 0; j < history.getSubjects().size(); j++) {
				
				subjectMatches[i][j] = group.matches(history.getSubjects().get(j));
				remainingGroupCredits[i][j] = group.getCredits();

			}
			sumOfCredits += group.getCredits();
		}
		backtracking(0, sumOfCredits,mandatoryDone);
//		if () {
			return createAllocation(history, mandatoryDone, allocatedSubjects);
//		} else {
//			return null;
//		}
	}

	public static boolean backtracking(int index, int remainingCredits, List<Subject> mandatoryDone) {
		// se os creditos restantes são 0, significa que todos os créditos
		// foram consumidos e portanto achamos uma solução
		if(remainingCredits==0){
			return true;
			// Se eu ja passei por esse estado, assim que eu entro num novo nivel da
			// iteração, significa que não há solução à partir desse nó
		}else if (index == history.getSubjects().size() || evaluatedStates.contains(createHashKey(index,
				remainingGroupCredits)) ) {
			return false;
		}

		List<SubjectGroup> electiveGroups = history.getAllocation()
				.getElectiveGroups();
		Subject subject = history.getSubjects().get(index);

		//copiamos os crédito do nosso pai
		if(index>0){
			for (int i = 0; i < electiveGroups.size(); i++) {
				remainingGroupCredits[i][index]=remainingGroupCredits[i][index-1];
			}
		}
		
		for (int i = 0; i < electiveGroups.size(); i++) {
			// Se nossa matéria puder ser encaixada no grupo e houver espaço a
			// ser consumido nesse grupo, alocamo-nas ali
			if (subjectMatches[i][index]
					&& remainingGroupCredits[i][index] > 0) {
				int delta = Math.min(remainingGroupCredits[i][index],
						subject.getCredits());

				remainingGroupCredits[i][index] -= delta;
				allocatedSubjects[index] = i;
				System.out.println("Nivel :" + index+". Encaixando a matéria "+ subject + " no grupo "+ i);
//				System.out.println("Créditos restantes = " + (remainingCredits-delta));
				System.out.println(createAllocation(history, mandatoryDone, allocatedSubjects));
				
				boolean found = backtracking(index + 1, remainingCredits
						- delta,mandatoryDone);
				if (found) {
					return true;
				}

				remainingGroupCredits[i][index] += delta;
			}
		}
		allocatedSubjects[index]=-1;
		if(backtracking(index+1, remainingCredits,mandatoryDone)){
			return true;
		}else{
			evaluatedStates.add(createHashKey(index, remainingGroupCredits));
			return false;
		}
	}

	public static String createHashKey(int index, int[][] groups) {
		String str = "";
		str = str + index;

		for (int i = 0; i < groups.length; i++) {
			str = str + "," + groups[i][index];
		}

		return str;
	}

	public static Allocation createAllocation(History history,
			List<Subject> mandatoryDone, int[] allocatedSubjects) {
		Allocation allocation = new Allocation();

		List<SubjectGroup> electiveGroups = allocation.getElectiveGroups();
		
		for (int i=0; i<history.getAllocation().getElectiveGroups().size()+1;i++) {
			electiveGroups.add(new SubjectGroup());
		}

		for (int i = 0; i < allocatedSubjects.length; i++) {
			Subject subject = history.getSubjects().get(i);
			if(allocatedSubjects[i]!=-1){
				electiveGroups.get(allocatedSubjects[i])
				.addCatalogueSubject(subject);
			}else{
				electiveGroups.get(electiveGroups.size()-1)
				.addCatalogueSubject(subject);
			}
		}
		
		allocation.getMandatorySubjects().getSubjects().addAll(mandatoryDone);

		return allocation;
	}

}
